#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
#http://www.careercup.com/question?id=13216725
#Facebook interview question
"""
An expression consisting of operands and binary operators can be written in Reverse Polish Notation (RPN) by writing both the operands followed by the operator. For example, 3 + (4 * 5) can be written as "3 4 5 * +".

You are given a string consisting of x's and *'s. x represents an operand and * represents a binary operator. It is easy to see that not all such strings represent valid RPN expressions. For example, the "x*x" is not a valid RPN expression, while "xx*" and "xxx**" are valid expressions. What is the minimum number of insert, delete and replace operations needed to convert the given string into a valid RPN expression?

Input: The first line contains the number of test cases T. T test cases follow. Each case contains a string consisting only of characters x and *.

Output: Output T lines, one for each test case containing the least number of operations needed.

Constraints: 1 <= T <= 100 The length of the input string will be at most 100.

Sample Input:

5
x
xx*
xxx**
*xx
xx*xx**
Sample Output:

0
0
0
2
0
Explanation:

For the first three cases, the input expression is already a valid RPN, so the answer is 0. For the fourth case, we can perform one delete, and one insert operation: xx -> xx -> xx
"""
from collections import defaultdict
def get_operation_count(expression, index):
    result = defaultdict(lambda: 10000)
    if index < 0: return result
    c = expression[index]
    items = get_operation_count(expression, index - 1)
    if not items: items[0] = 0
    for operand_count, change_count in items.iteritems():
        if c == 'x':
            result[operand_count + 1] = change_count
        else:
            if operand_count > 1: result[operand_count - 1] = change_count
            elif operand_count == 1:
                result[1] = min(result[1], change_count + 1)
                result[2] = min(result[2], change_count + 1)
            else:
                result[0] = min(result[0], change_count + 1)
                result[1] = min(result[1], change_count + 1)
    return result

def calculate_min_change_count(expression):
    items = get_operation_count(expression, len(expression) - 1)
    result = 10000
    for operand_count, change_count in items.iteritems():
        result = min(operand_count / 2 + change_count, result)
    return result

def convert_str(arr):
    result = []
    for i in arr:
        result.append(i == 0 and "x" or "*")
    return "".join(result)


from utils import *
for i in range(0, 10):
    arr = random_arr(10, 0, 1)
    expression = convert_str(arr)
    print expression, calculate_min_change_count(expression)
